package top.byfree.sort;

import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 80000000);
        }
        long l = System.currentTimeMillis();
        radixSort(arr);
        long l2 = System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println(l2 - l);

//        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0, 3};
//        long l = System.currentTimeMillis();
//        radixSort(arr);
//        long l2 = System.currentTimeMillis();
////        System.out.println(Arrays.toString(arr));
//        System.out.println(l2 - l);
    }

    public static void radixSort(int[] arr) {
        // 数组中最大的数的位数
        int max = arr[0]; // 假设第一个数是最大的

        for (int i = 1; i < arr.length; i++) {
            if (i > max) {
                max = arr[i];
            }
        }
        // 的到最大数是几位数
        int maxLength = (max + "").length();


        //定义一个二维数组，表示十个桶
        int[][] bucket = new int[10][arr.length];

        int[] bucketElementCounts = new int[10];
        // 使用循环将代码处理

        for (int z = 0, n = 1; z < maxLength; z++, n *= 10) {
            for (int i = 0; i < arr.length; i++) {
                int digitOfElement = arr[i] / n % 10;
                // 放在对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]++] = arr[i];
            }
            // 取数据
            int index = 0;
            // 遍历每一个桶，将桶中的数据放到原数组
            for (int i = 0; i < bucketElementCounts.length; i++) {
                if (bucketElementCounts[i] != 0) {
                    // 循环该桶
                    for (int j = 0; j < bucketElementCounts[i]; j++) {
                        // 取出元素放入到arr
                        arr[index++] = bucket[i][j];
                    }
                }
                bucketElementCounts[i] = 0;
            }
        }



    }
}
